package mornd.binarysearch;

/**
 * @author: mornd
 * @dateTime: 2023/5/30 - 11:52
 * 二分查找 (增强)
 */
public class Demo2 {
    public static void main(String[] args) {
//        int[] arr = {1, 3, 6, 8, 9};
//        int i = binarySearch(6, arr);
//        System.out.println(i);

        int[] arr = {0, 1, 1, 1, 3, 6, 8, 9, 9, 11};
        int i = rightMost(8, arr);
        System.out.println(i);
    }

    // 常规版
    private static int binarySearch(int target, int[] arr) {
        int low = 0, high = arr.length - 1, mid;
        while (low < high) {
            mid = (low + high) >>> 1;
            if (target < arr[mid]) {
                high = mid - 1;
            } else if (target > arr[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    // 平衡版，减少循环内的if else比较
    static int balance(int target, int[] arr) {
        int i = 0, j = arr.length;
        while (1 < j - i) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        if (arr[i] == target) {
            return i;
        } else {
            return -1;
        }
    }


    // 数组中存在相同元素时，返回与之匹配元素的最左边元素下标
    static int leftMost(int target, int[] arr) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= arr[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }

    // 数组中存在相同元素时，查找与之匹配的最右边元素下标
    static int rightMost(int target, int[] arr) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target >= arr[m]) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i - 1;
    }
}
